/**
 * 当钱包的算法都是已经做过 重新用kotlin 复习一下
 */
package com.zbxx.leetcode.kt

import kotlin.math.max

/**
 * 搜索二维矩阵
 * 逐行二分
 * @date 2022/2/16
 */
fun searchMatrix(matrix: Array<IntArray>, target: Int): Boolean {
    var endIdx = matrix[0].size - 1
    for (intArray in matrix) {
        var idx = binarySearch(intArray, 0, endIdx, target)
        if (idx == -1) {
            return false
        }
        endIdx = if (intArray[idx] == target) {
            return true
        } else if (intArray[idx] > target) {
            idx-1
        } else {
            idx
        }
    }
    return false
}

fun binarySearch(arr: IntArray, begin: Int, end: Int, target: Int): Int {
    if (begin > end) {
        return -1
    }
    if (begin == end) {
        return begin
    }
    var begin = begin
    var end = end
    var mid = 0
    while (begin < end) {
        mid = begin + (end - begin) / 2
        if (arr[mid] > target) {
            end = mid - 1
        } else if (arr[mid] < target) {
            begin = mid + 1
        } else {
            return mid
        }
    }
    return begin;
}


/**
 * 合并两个有序数组
 */

fun merge(nums1: IntArray, m: Int, nums2: IntArray, n: Int): Unit {
    if(m==0){
        for(i in 0 until n){
            nums1[i] = nums2[i]
        }
        return
    }
    if(n==0){return}
    var mergedIdx = nums1.size-1
    var mgIdx = m-1
    var anotherIdx = n-1
    while(mgIdx>=0&&anotherIdx>=0){
        if(nums1[mgIdx]>=nums2[anotherIdx]){
            nums1[mergedIdx--] = nums1[mgIdx--]
        }else{
            nums1[mergedIdx--] = nums2[anotherIdx--]
        }
    }
    if(mergedIdx>=0){
        if(mgIdx<0){
            while (mergedIdx>=0){
                nums1[mergedIdx--] = nums2[anotherIdx--]
            }
        }else{
            while (mergedIdx>=0){
                nums1[mergedIdx--] = nums1[mgIdx--]
            }
        }
    }
    return
}




fun main(args: Array<String>) {
/*    val matrix = Array(5, init = { IntArray(5) })
    matrix[0] = intArrayOf(1, 4, 7, 11, 15)
    matrix[1] = intArrayOf(2, 5, 8, 12, 19)
    matrix[2] = intArrayOf(3, 6, 9, 16, 22)
    matrix[3] = intArrayOf(10, 13, 14, 17, 24)
    matrix[4] = intArrayOf(18, 21, 23, 26, 30)
    println(searchMatrix(matrix, 24))*/


    val nums1 = intArrayOf(1,2,3,0,0,0)
    val nums2 = intArrayOf(2,5,6)
    merge(nums1,3,nums2,3)
    nums1.forEach { print(it) }
}